package com.cty.twentySecondDay;
/*
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
*/

import java.util.Stack;

public class Q_29 {
    // 力扣官方题解 方法一:计算链表长度
    /*
    * 思路:
    *   我们定义一个哑节点 让他的next指向head
    *   我们计算出链表长度Length(没有哑节点) 要删除的节点在Length - n + 1（从head开始遍历）
    *   从哑节点开始遍历的话正好要删除的节点的前一个节点在Length - n + 1
    *   时间复杂度O(L) L是链表的长度 空间复杂度O(1)
    * */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        // 计算链表的长度
        int Length = 0;
        ListNode temp = head;
        while (temp != null) {
            Length++;
            temp = temp.next;
        }
        // 计算出长度 寻找要删除的节点的前一个节点
        temp = dummy;
        for (int i = 1;i <Length - n + 1;i++) {
            temp = temp.next;
        }
        // 找到就修改
        temp.next = temp.next.next;
        // 返回哑节点的第二个节点
        return dummy.next;
    }

    // 力扣官方题解 方法二:栈
    /*
    * 思路: 我们将所有的节点遍历加入栈中 根据栈先入后出的原则
    *   我们只需要将第n个节点删除即可
    * 时间复杂度O(L) 空间复杂度O(L) L是链表的长度
    * */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        // 创建一个哑节点
        ListNode dummy = new ListNode(0, head);
        if (head == null) return null;
        Stack<ListNode> listNodes = new Stack<>();
        ListNode cur = dummy;
        // 遍历将链表的所有节点加入栈中
        while (cur != null) {
            listNodes.push(cur);
            cur = cur.next;
        }
        // 取出删除节点
        for (int i = 0;i < n;i++) {
            listNodes.pop();
        }
        // 找到要删除节点的前一个节点
        ListNode prev = listNodes.peek();
        // 删除节点
        prev.next = prev.next.next;
        // 返回结果
        return dummy.next;
    }

    // 力扣官方题解 方法三:双指针
    /*
    * 思路：定义两个指针first second 在链表的前面加一个哑节点
    *   让second指向哑节点 first指向second前面的第n个节点
    *   使二者中间相差n-1个节点 当first为最后一个节点时 second
    *   刚好指向要删除节点的前一个节点 然后直接删除即可
    *   时间复杂度O(L) 空间复杂度O(1) L是链表的长度
    * */
    public ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode second = dummy;
        ListNode first = dummy;
        // 将第一个指针向前遍历 使其相差n-1
        for (int i = 0;i < n;i++) {
            first = first.next;
        }
        // 让两个指针向前走
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        // 此时的second 是要删除节点的前一个节点
        second.next = second.next.next;
        return dummy.next;
    }
}

